package com.lzq.leetcode.hoot100;

import java.util.*;

public class s207 {

    public boolean canFinish(int numCourses, int[][] prerequisites) {

        int n = prerequisites.length;
        int[] pre = new int[numCourses];    // 记录课程的先修课程数
        Deque<Integer> canStar = new LinkedList<>();
        // 构造图 寻找关系
        List<List<Integer>> map = new ArrayList<>();
        for (int i=0; i<n; i++) {

            int a = prerequisites[i][0];
            int b = prerequisites[i][1];

            pre[b]++;
            map.get(a).add(b);
        }
        // 记录能够开始修习的课程
        for (int i=0; i<numCourses; i++) {
            if (pre[i] == 0) {
                canStar.push(i);
            }
        }
        // 深度优先搜索检查是否有环
        int learned = 0;
        while (!canStar.isEmpty()) {
            ++learned;
            int learn = canStar.pop();
            // 减少度
            List<Integer> nextCourse = map.get(learn);
            for (int c : nextCourse) {
                --pre[c];
                if (pre[c] == 0) {
                    canStar.push(c);
                }
            }
        }

        // 判断是否有课没学完
        return learned == numCourses;
    }
}
